/*
 * Backtracking.c
 *
 *  Created on: 05/08/2013
 *      Author: marcio
 */

#include "Backtracking.h"

long Backtracking(
		void* (*aloca)(),
		void (*release)(void*),
		int (*sel)(void*, long),
		int (*gen)(void*, long*),
		int (*root)(void*),
		long n,
		long long* nd
){
	long long imax = 0;
	long q = 0;
	long ind;
	poll = malloc(n*sizeof(void*));
	long long nodes = 0;

	for(long i = 0; i < n+1; i++){
		poll[i] = aloca();
	}

	root(poll[0]);

	while(q >= 0){
		if(select(poll[q], imax)){
			ind = gen( poll[q+1], &imax);
			if(ind != 0){
				q++;
				nodes++;
			}
		}else q--;
	}

	for(long i = 0; i < n+1; i++){
		release(poll[i]);
	}
	*nd = nodes;
	return imax;
}
